const int SZ = 2e6 + 20;// 二倍空间
const int ALP = 26 + 10;// 字符集大小

struct SAM {
    int tree[SZ][ALP], fail[SZ], len[SZ], cnt[SZ];
    int tot, last;

    SAM() {tot = 1; last = 1; len[1] = 0;}

    void ins(char x) {// 插入字符
        x -= 'a';
        int u = ++tot, p = last;
        len[u] = len[last] + 1; last = u; cnt[u] = 1;
        while (p && !tree[p][x]) tree[p][x] = u, p = fail[p];
        if (!p) fail[u] = 1;
        else {
            int q = tree[p]][x];
            if (len[q] = len[p] + 1) fail[u] = q;
            else {
                int cq = ++tot;
                len[cq] = len[p] + 1; fail[cq] = fail[q]; cnt[cq] = 0;
                fail[u] = fail[q] = cq;
                memcpy(tree[cq], tree[q], sizeof tree[q]);
                while (p && tree[p][x] == q) tree[p][x] = cq, p = fail[p];
            }
        }
    }
} sam;